Masala #0650

$K$ ranglardan foydalanib $N \times M$ panjarani rang berish usullari sonini hisoblang. Panjaradagi qo'shni kvadratlar bir xil ranglarga ega bo'lishi mumkin. Sizning vazifangiz $K$ ranglarda foydalanib ushbu panjarani eng kam bo'yash usulini toping.

• Birinchi qatorda $T (1 \le T \le 15)$  testlar soni kiritiladi.
• Keyingi T ta qatorda $N,M (1 \le N , M \le 8)$ va $K (1 \le K \le 10^{18})$ sonlari kiritiladi.

Chiqish faylining birinchi qatorida har bir test uchun natijalarni probel bilan ajratilingan holda chop eting